<?php
// 二分查找：x 平方根的整数部分 ans 是满足 k^2 < x, 因此我们可以对 k进行二分查找，从而得到答案
class Solution {
    public function mySqrt($x) {
        $l = 0;
        $r = $x;
        $ans = -1;
        while ($l <= $r) {
            $mid = $l + ($r - $l) / 2;
            if ($mid * $mid <= $x) {
                $ans = $mid;
                $l = $mid + 1;
            } else {
                $r = $mid - 1;
            }
        }
        return $ans;
    }
}